﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
// 原题连接：https://leetcode.cn/problems/odd-even-linked-list/
/*
题目描述：
给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。
第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。
请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。
你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。
*/


 // Definition for singly-linked list.
 struct ListNode {
     int val;
     struct ListNode *next;
};
 


struct ListNode* oddEvenList(struct ListNode* head) {
    if (NULL == head || NULL == head->next) {
        return head;
    }
    struct ListNode* cur = head;
    int len = 0;
    struct ListNode* oddHead = NULL;
    struct ListNode* oddTail = NULL;
    struct ListNode* evenHead = NULL;
    struct ListNode* evenTail = NULL;

    while (cur) {
        len++;
        if (len % 2 == 1) {
            if (NULL == oddHead) {
                oddHead = cur;
                oddTail = cur;
            }
            else {
                oddTail->next = cur;
                oddTail = oddTail->next;
            }
        }
        else {
            if (NULL == evenHead) {
                evenHead = cur;
                evenTail = cur;
            }
            else {
                evenTail->next = cur;
                evenTail = evenTail->next;
            }
        }
        cur = cur->next;
    }
    evenTail->next = NULL;
    oddTail->next = evenHead;
    return oddHead;
}